﻿#include <vector>
#include <algorithm>

using namespace std;


/*
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。


示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。


示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
 

提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
*/






class Solution {
public:
	int trap(vector<int>& height) {
		vector<int> left(height.size() + 10);
		vector<int> right(height.size() + 10);

		for (int i = 0; i < height.size(); i++) {
			if (i == 0) left[i] = 0;
			else {
				left[i] = max(left[i - 1], height[i - 1]);
			}
		}

		for (int i = height.size() - 1; i >= 0; i--) {
			if (i == height.size() - 1) right[i] = 0;
			else {
				right[i] = max(right[i+1],height[i+1]);
			}
		}

		int ans = 0;
		for (int i = 0; i < height.size(); i++) {
			if (height[i] <= min(left[i], right[i])) {
				ans += min(left[i], right[i]) - height[i];
			}
		}

		return ans;
	}
};



//int main() {
//	Solution s;
//	vector<int> v{ 4,2,0,3,2,5 };
//	s.trap(v);
//	return 0;
//}